import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2020/6/4 下午 09:37
 */
public class month2006 {

    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // right 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int right = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * right;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            right *= nums[i];
        }
        return answer;
    }

    public int[] productExceptSelf2(int[] nums) {
        int[] ret = new int[nums.length];
        Arrays.fill(ret, 1);
        int left = 1, right = 1;
        for (int i = 0; i < nums.length; i++) {
            ret[i] *= left;
            left *= nums[i];

            ret[nums.length - 1 - i] *= right;
            right *= nums[nums.length - 1 - i];
        }
        return ret;
    }

    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[]{};
        }
        int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int row = matrix.length;
        int col = matrix[0].length;
        int[] ret = new int[row * col];
        boolean[][] visited = new boolean[row][col];
        int i = 0, j = 0, index = 0, temp = 0;
        while (index < row * col) {
            ret[index++] = matrix[i][j];
            visited[i][j] = true;
            int nextRow = i + direction[temp % 4][0];
            int nextCol = j + direction[temp % 4][1];
            boolean flag = nextRow == row || nextCol == col || nextRow < 0 || nextCol < 0 || visited[nextRow][nextCol];
            if (flag) {
                temp++;
                nextRow = i + direction[temp % 4][0];
                nextCol = j + direction[temp % 4][1];
            }
            i = nextRow;
            j = nextCol;
        }
        return ret;
    }

    public int[] shuffle(int[] nums, int n) {
        int length = nums.length;
        int index = 0;
        int[] ret = new int[length];
        for (int i = 0; i < length / 2; i++) {
            ret[index++] = nums[i];
            ret[index++] = nums[length / 2 + i];
        }
        return ret;
    }

    public int[] getStrongest(int[] arr, int k) {
        int length = arr.length;
        int midIndex = (length - 1) / 2;
        Arrays.sort(arr);
        int mid = arr[midIndex];
        List<Integer> list = new ArrayList<>(arr.length);
        for (int num : arr) {
            list.add(num);
        }
        list.sort(Comparator.comparingInt(o -> Math.abs(o - mid)));
        System.out.println(Arrays.toString(list.toArray()));
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = list.get(length - 1 - i);
        }
        return ret;
    }

    static class BrowserHistory {

        private final Stack<String> stackX;

        private final Stack<String> stackY;

        private final String homepage;

        public BrowserHistory(String homepage) {
            this.homepage = homepage;
            this.stackX = new Stack<>();
            this.stackY = new Stack<>();
            this.stackX.push(homepage);
        }

        public void visit(String url) {
            this.stackX.push(url);
            this.stackY.clear();
        }

        public String back(int steps) {
            if (steps > this.stackX.size()) {
                steps = this.stackX.size();
            }
            while (steps > 0) {
                String pop = this.stackX.pop();
                this.stackY.push(pop);
                steps--;
            }
            if (this.stackX.empty()) {
                this.stackX.push(homepage);
            }
            return this.stackX.peek();
        }

        public String forward(int steps) {
            if (steps > this.stackY.size()) {
                steps = this.stackY.size();
            }
            while (steps > 0) {
                String pop = this.stackY.pop();
                this.stackX.push(pop);
                steps--;
            }
            return this.stackX.peek();
        }
    }


    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int res = -1;
        int[][][] dp = new int[m][target + 1][n];
        for (int c = 0; c < n; c++) {
            int r = min(houses, cost, m, n, 0, c, target, dp);
            if (r != -1) {
                if (res == -1) {
                    res = r;
                } else {
                    res = Math.min(res, r);
                }
            }
        }
        return res;
    }

    private int min(int[] houses, int[][] cost, int m, int n, int h, int c, int t, int[][][] dp) {
        if (t <= 0) {
            return -1;
        }
        if (dp[h][t][c] != 0) {
            return dp[h][t][c];
        }

        int res = -1;
        if (h == m - 1) {
            if (t == 1) {
                if (houses[h] == 0) { // not paint
                    res = cost[h][c];
                } else if (houses[h] - 1 == c) { // same color
                    res = 0;
                }
            }
            dp[h][t][c] = res;
            return res;
        }
        if (m - h < t) {
            dp[h][t][c] = res;
            return res;
        }

        // not last house, enough house for target
        if (houses[h] != 0) {
            if (houses[h] - 1 == c) {
                for (int nc = 0; nc < n; nc++) {
                    int r = min(houses, cost, m, n, h + 1, nc, nc == c ? t : t - 1, dp);
                    if (r != -1) {
                        if (res == -1) {
                            res = r;
                        } else {
                            res = Math.min(res, r);
                        }
                    }
                }
            }
            dp[h][t][c] = res;
            return res;
        }

        // not last house, enough houses for target, not paint yet
        for (int nc = 0; nc < n; nc++) {
            int r = min(houses, cost, m, n, h + 1, nc, nc == c ? t : t - 1, dp);
            if (r != -1) {
                if (res == -1) {
                    res = r + cost[h][c];
                } else {
                    res = Math.min(res, r + cost[h][c]);
                }
            }
        }
        dp[h][t][c] = res;
        return res;
    }


    class Solution {
        private static final int INF = 1 << 20;
        private final Map<String, Integer> wordId; // 单词到id的映射
        private final ArrayList<String> idWord; // id到单词的映射
        private ArrayList<Integer>[] edges; // 图的边

        public Solution() {
            wordId = new HashMap<>();
            idWord = new ArrayList<>();
        }

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            int id = 0;
            // 将wordList所有单词加入wordId中 相同的只保留一个 // 并为每一个单词分配一个id
            for (String word : wordList) {
                if (!wordId.containsKey(word)) {
                    wordId.put(word, id++);
                    idWord.add(word);
                }
            }
            // 若endWord不在wordList中 则无解
            if (!wordId.containsKey(endWord)) {
                return new ArrayList<>();
            }
            // 把beginWord也加入wordId中
            if (!wordId.containsKey(beginWord)) {
                wordId.put(beginWord, id++);
                idWord.add(beginWord);
            }

            // 初始化存边用的数组
            edges = new ArrayList[idWord.size()];
            for (int i = 0; i < idWord.size(); i++) {
                edges[i] = new ArrayList<>();
            }
            // 添加边
            for (int i = 0; i < idWord.size(); i++) {
                for (int j = i + 1; j < idWord.size(); j++) {
                    // 若两者可以通过转换得到 则在它们间建一条无向边
                    if (transformCheck(idWord.get(i), idWord.get(j))) {
                        edges[i].add(j);
                        edges[j].add(i);
                    }
                }
            }

            int dest = wordId.get(endWord); // 目的ID
            List<List<String>> res = new ArrayList<>(); // 存答案
            int[] cost = new int[id]; // 到每个点的代价
            for (int i = 0; i < id; i++) {
                cost[i] = INF; // 每个点的代价初始化为无穷大
            }

            // 将起点加入队列 并将其cost设为0
            Queue<ArrayList<Integer>> q = new LinkedList<>();
            ArrayList<Integer> tmpBegin = new ArrayList<>();
            tmpBegin.add(wordId.get(beginWord));
            q.add(tmpBegin);
            cost[wordId.get(beginWord)] = 0;

            // 开始广度优先搜索
            while (!q.isEmpty()) {
                ArrayList<Integer> now = q.poll();
                int last = now.get(now.size() - 1); // 最近访问的点
                if (last == dest) { // 若该点为终点则将其存入答案res中
                    ArrayList<String> tmp = new ArrayList<>();
                    for (int index : now) {
                        tmp.add(idWord.get(index)); // 转换为对应的word
                    }
                    res.add(tmp);
                } else { // 该点不为终点 继续搜索
                    for (int i = 0; i < edges[last].size(); i++) {
                        int to = edges[last].get(i);
                        // 此处<=目的在于把代价相同的不同路径全部保留下来
                        if (cost[last] + 1 <= cost[to]) {
                            cost[to] = cost[last] + 1;
                            // 把to加入路径中
                            ArrayList<Integer> tmp = new ArrayList<>(now);
                            tmp.add(to);
                            q.add(tmp); // 把这个路径加入队列
                        }
                    }
                }
            }
            return res;
        }

        // 两个字符串是否可以通过改变一个字母后相等
        boolean transformCheck(String str1, String str2) {
            int differences = 0;
            for (int i = 0; i < str1.length() && differences < 2; i++) {
                if (str1.charAt(i) != str2.charAt(i)) {
                    ++differences;
                }
            }
            return differences == 1;
        }
    }

    public int[] runningSum(int[] nums) {
        int temp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            temp += nums[i];
            nums[i] = temp;
        }
        return nums;
    }

    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> keyMap = new HashMap<>();
        Map<Integer, Integer> tempMap = new HashMap<>();
        for (int num : arr) {
            Integer orDefault = keyMap.getOrDefault(num, 0);
            orDefault++;
            keyMap.put(num, orDefault);
            tempMap.put(num, orDefault);
        }
        int temp = 1;
        while (k > 0 && tempMap.size() > 0) {
            for (Map.Entry<Integer, Integer> entry : keyMap.entrySet()) {
                Integer key = entry.getKey();
                Integer value = entry.getValue();
                if (value == temp) {
                    k -= value;
                    if (k >= 0) {
                        tempMap.remove(key);
                    }
                }
            }
            temp++;
        }
        return tempMap.size();
    }

    public int minDays(int[] bloomDay, int m, int k) {
        if (m * k > bloomDay.length) {
            return -1;
        }
        int low = 1, high = (int) 1e9;
        int ret = -1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (check(bloomDay, m, k, mid)) {
                ret = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ret;
    }

    private boolean check(int[] bloomDay, int m, int k, int mid) {
        int count = 0, length = 0;
        for (int bloom : bloomDay) {
            if (bloom <= mid) {
                length++;
                if (length == k) {
                    count++;
                    length -= k;
                }
            } else {
                length = 0;
            }
        }
        return count >= m;
    }

    static class TreeAncestor {

        private final Map<Integer, List<Integer>> map;

        public TreeAncestor(int n, int[] parent) {
            map = new HashMap<>(n);
            for (int i = 0; i < parent.length; i++) {
                int num = parent[i];
                if (num == -1) {
                    map.put(i, new ArrayList<>());
                } else {
                    List<Integer> orDefault = map.getOrDefault(i, new ArrayList<>());
                    orDefault.add(num);
                    if (map.containsKey(num)) {
                        List<Integer> list = map.get(num);
                        if (list.size() > 0) {
                            orDefault.addAll(list);
                        }
                    }
                    map.put(i, orDefault);
                }
            }
        }

        public int getKthAncestor(int node, int k) {
            if (!map.containsKey(node)) {
                return -1;
            }
            List<Integer> list = map.get(node);
            if (list.size() < k) {
                return -1;
            }
            return list.get(k - 1);
        }
    }

    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfsTree(root);
        return maxSum;
    }

    private int dfsTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = Math.max(dfsTree(root.left), 0);
        int right = Math.max(dfsTree(root.right), 0);

        maxSum = Math.max(maxSum, left + right + root.val);

        return root.val + Math.max(left, right);
    }

    public int xorOperation(int n, int start) {
        int ret = start;
        for (int i = 1; i < n; i++) {
            int temp = start + 2 * i;
            ret = ret ^ temp;
        }
        return ret;
    }

    //    private HashSet<String> nameSet = new HashSet<>();
//    private HashMap<String, Integer> nameValueMap = new HashMap<>();
    public String[] getFolderNames(String[] names) {
        Set<String> nameSet = new HashSet<>();
        HashMap<String, Integer> nameValueMap = new HashMap<>();
        String[] ret = new String[names.length];

        for (int i = 0; i < names.length; i++) {
            String name = names[i];
            if (nameSet.contains(name)) {
                int num = nameValueMap.getOrDefault(name, 1);
                StringBuilder sb = new StringBuilder(name);
                sb.append('(').append(num).append(')');
                while (nameSet.contains(sb.toString())) {
                    num += 1;
                    sb = new StringBuilder(name);
                    sb.append('(').append(num).append(')');
                }
                nameValueMap.put(name, num);
                nameSet.add(sb.toString());
                ret[i] = sb.toString();
            } else {
                nameSet.add(name);
                ret[i] = name;

            }
        }
        return ret;
    }

    public int[] avoidFlood(int[] rains) {
        // (已满的湖泊, 上次降雨日)
        Map<Integer, Integer> rainMap = new HashMap<>();
        // 可选的抽日
        int[] days = new int[rains.length];
        Arrays.fill(days, -1);
        int[] res = new int[rains.length];
        for (int i = 0, dayNum = 0; i < rains.length; i++) {
            int lake = rains[i];
            if (lake > 0) {
                res[i] = -1;
                if (!rainMap.containsKey(lake)) {
                    // lake 为空
                    rainMap.put(lake, i);
                } else {
                    // lake 已满
                    // 选择尽早的可抽日
                    boolean done = false;
                    for (int day = 0, last = rainMap.get(lake); day < dayNum; day++) {
                        if (days[day] < last) {
                            continue;
                        }
                        res[days[day]] = lake;
                        days[day] = -1;
                        rainMap.put(lake, i);
                        done = true;
                        break;
                    }
                    if (!done) {
                        // 没有可选的抽日
                        return new int[0];
                    }
                }
            } else {
                // 可抽日
                days[dayNum++] = i;
                res[i] = 1;
            }
        }
        return res;
    }

    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        return null;
    }

    public static void main(String[] args) {
        month2006 month2006 = new month2006();
        month2006.getFolderNames(new String[]{"wano", "wano", "wano", "wano"});
    }
}
